Routing in large integrated circuits or electronic networks is automatically performed by a routing mechanism known as a “router” which is typically implemented as a software tool on a computer-aided design (CAD) system.
In a CAD system, modern routers try to identify routing paths through a routing resource graph. These routers primarily consider various routing alternatives available in the resource graph prior to routing. Each routing alternative available in the resource graph comprises nets which further comprise a combination of sources and sinks.
The routing resource graph is a data structure that establishes links between a set of nodes (also called vertices) and a set of edges. It is represented by G (V, E), where vertex vεV, represents a grid cell, a node or a conductor (e.g., wire) and each edge eεE, corresponds to a boundary between two adjacent grid cells, nodes or wires.
Typical operations associated with routing resource graphs are: finding a path between two nodes and finding the shortest path from one node to another.
Dijkstra's shortest path routing method is one known method for single-source shortest path routing (see, Dijkstra, E. W. (1959) “A note on two problems in connection with graphs” Numerische Mathematik 1: 269-271; and Cormen, et al (2001) “Section 24.3: Dijkstra's algorithm” Introduction to Algorithms (Second ed.), MIT Press and McGraw-Hill, pp. 595-601; the disclosures of which are hereby incorporated by reference). It computes length of the shortest path from the source to each of the remaining vertices in the graph. Dijkstra's method determines the distances (costs) between a given vertex and remaining vertices in a graph. This method begins at a specific vertex and extends outward within the graph, until all vertices have been reached. The process of visiting all nodes in a graph is known as graph traversal.
However, Dijkstra routing method used in its original/unmodified form as known to those skilled in the art searches the entire graph in order to construct the routing tree, due to which this method results in increased run time complexity and reduced performance of the router by visiting all the vertices in every execution.